"""先将整个待排序的记录序列分割成若干子序列分别进行直接排序，待整个序列中的记录基本有序时再对
全体记录进行依次直接插入排序"""
def shellSort(alist):
    sublistcount = len(alist)//2
    while sublistcount > 0:
        for startposition in range(sublistcount):
            gapInsertionSort(alist,startposition,sublistcount)
        sublistcount = sublistcount//2
    return alist



def gapInsertionSort(alist,start,gap):                         #有间隙的插入排序
    for i in range(start+gap,len(alist),gap):
        currentvalue = alist[i]
        position = i
        while position >= gap and alist[position-gap] > currentvalue:
            alist[position] = alist[position-gap]
            position = position - gap
        alist[position] = currentvalue


print(shellSort([5,4,3,2,1]))